import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author CoderXshuai
 * @date 2021/8/28 21:19
 */
public class AllRoadsLeadtoRome {
    static int least = Integer.MAX_VALUE;
    static Places places;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] line = reader.readLine().split(" ");
        int cityNum = Integer.parseInt(line[0]);
        int routeNum = Integer.parseInt(line[1]);
        String cityStart = line[2];
        Map<Integer, Integer> hapMap = new HashMap<>((int) (cityNum / 0.75) + 1);
        places = new Places(cityNum);
        places.put(cityStart);
        for (int i = 1; i < cityNum; i++) {
            line = reader.readLine().split(" ");
            places.put(line[0]);
            hapMap.put(places.getID(line[0]), Integer.parseInt(line[1]));
        }
        int[][] route = new int[cityNum + 1][cityNum + 1];
        for (int i = 0; i < routeNum; i++) {
            line = reader.readLine().split(" ");
            route[places.getID(line[0])][places.getID(line[1])] = Integer.parseInt(line[2]);
            route[places.getID(line[1])][places.getID(line[0])] = Integer.parseInt(line[2]);
        }
        reader.close();
        List<List<Integer>> res = backtrack(route, cityNum, places.getID(cityStart));
        int hapMax = 0;
        int hapAvg = 0;
        List<Integer> output = new LinkedList<>();
        for (List<Integer> item : res) {
            int tempSum = 0;
            for (Integer i : item) {
                tempSum += hapMap.getOrDefault(i, 0);
            }
            int tempAvg = tempSum / (item.size() - 1);
            if (tempSum > hapMax) {
                hapMax = tempSum;
                hapAvg = tempAvg;
                output = item;
            }
            if (tempSum == hapMax) {
                if (tempAvg > hapAvg) {
                    hapAvg = tempAvg;
                    output = item;
                }
            }
        }
        System.out.println(res.size() + " " + least + " " + hapMax + " " + hapAvg);
        for (Integer integer : output) {
            String place = places.getName(integer);
            System.out.print(place);
            if (!"ROM".equals(place))
                System.out.print("->");
        }
    }

    public static List<List<Integer>> backtrack(int[][] route, int cityNum, int cityStart) {
        int[] distances = new int[cityNum];
        Map<Integer, List<List<Integer>>> res = new HashMap<>((int) Math.ceil(cityNum / 0.75));
        //初始化，把0加入到res中
        List<Integer> start = new LinkedList<>();
        start.add(0);
        List<List<Integer>> times = new LinkedList<>();
        times.add(start);
        res.put(0, times);
        Set<Integer> visited = new HashSet<>((int) Math.ceil(cityNum / 0.75));
        Queue<Integer> q = new LinkedList<>();
        q.add(cityStart);
        while (!q.isEmpty()) {
            Integer cur = q.poll();
            if (visited.contains(cur))
                continue;
            visited.add(cur);
            int[] choices = route[cur];
            for (int i = 0; i < choices.length; i++) {
                if (choices[i] != 0) {
                    if (distances[i] == 0 && i != 0) {
                        distances[i] = Integer.MAX_VALUE;
                    }
                    int sum = distances[cur] + choices[i];
                    if (sum < distances[i]) {
                        Map<Integer, List<List<Integer>>> listMap = new HashMap<>(res);
                        distances[i] = sum;
                        //获取之前的路线
                        List<List<Integer>> tempList = new LinkedList<>(listMap.get(cur));
                        int sz = tempList.size();
                        for (int j = 0; j < sz; j++) {
                            List<Integer> integers = new LinkedList<>(tempList.get(j));
                            integers.add(i);
                            tempList.set(j, integers);
                        }
                        res.put(i, new LinkedList<>(tempList));
                    } else if (sum == distances[i]) {
                        Map<Integer, List<List<Integer>>> listMap = new HashMap<>(res);
                        distances[i] = sum;
                        //获取之前的路线
                        List<List<Integer>> tempList = new LinkedList<>(listMap.get(cur));
                        int sz = tempList.size();
                        for (int j = 0; j < sz; j++) {
                            List<Integer> integers = new LinkedList<>(tempList.get(j));
                            integers.add(i);
                            tempList.set(j, integers);
                        }
                        res.getOrDefault(i, new LinkedList<>()).addAll(new LinkedList<>(tempList));
                    }
                    q.offer(i);
                }
            }
        }
        //最短路径计算完毕，计算快乐值
        least = distances[places.getID("ROM")];
        return res.get(places.getID("ROM"));
    }
}

class Places {
    String[] names;
    int last = 0;
    private Map<String, Integer> map;

    public Places(int size) {
        names = new String[size];
        map = new HashMap<>((int) (size / 0.75) + 1);
    }

    public void put(String name) {
        names[last] = name;
        map.put(name, last);
        last++;
    }

    public int getID(String name) {
        return map.getOrDefault(name, -1);
    }

    public String getName(int id) {
        return names[id];
    }
}
